package com.zjj.algorithm.learning.atguigu.sort;

import java.util.Arrays;

/**
 * 快速排序
 *使用选择排序，排 80000 个数据，用时 18 ms，在大数据量下，比 希尔排序更优一点
 * 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
 *
 * 1、从数列中挑出一个元素，称为 “基准”（pivot）；
 * 2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 *    在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 * 3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 *
 * @author zjj_admin
 * @date 2022/11/16 9:39
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2,5,1,4,3,6,1,3,2};
        quickSort(arr,0,arr.length - 1);

        System.out.println("arr = " + Arrays.toString(arr));


        //测试排 80000 个数据用时
//        int[] arr = new int[80000];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random() * 800000);
//        }
//        long time1 = System.currentTimeMillis();
//
//        quickSort(arr,0,arr.length - 1);
//        long time2 = System.currentTimeMillis();
////        System.out.println("arr = " + Arrays.toString(arr));
//        System.out.printf("使用选择排序，排 %d 个数据，用时 %s ms", arr.length, (time2 - time1));

    }

    public static void quickSort(int[] array , int left , int right){


        //左下标
        int l = left;
        //右下标
        int r = right;
        int pivot = array[(left + right) / 2];
        int temp;
        while (l < r){
            //从左边向右边依次寻找，找到一个大于 pivot 的坐标
            while (array[l] < pivot){
                l ++;
            }

            //从右边向左边依次寻找，找到一个小于 pivot 的坐标
            while (array[r] > pivot){
                r --;
            }
            //当 l = r 时，说明没有找到，说明已经有序，直接退出即可
            if(l >= r){
                break;
            }
            //当找到了对应的 a[l] 和 a[r]，交换 a[l] 和 a[r]
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;

            //当交换以后，若发现 a[l] == a[pivot] 那么就将 r 向前移动
            if(array[l] == pivot){
                r --;
            }

            if(array[r] == pivot){
                l ++;
            }
        }

         //System.out.println("排序过程：" + Arrays.toString(array));
        // 若 l == r ,则必须 l++，r-- 否则陷入死循环，导致栈溢出
        if( l == r){
            l ++;
            r --;
        }

        // 依次向左边递归
        if(left < r){
            quickSort(array,left,r);
        }
        //向右递归
        if(right > l){
            quickSort(array,l,right);
        }


    }
}
